DROPS

Document

Track A: Algorithms, Complexity and Games

DOI: 10.4230/LIPIcs.ICALP.2020.63

Feasible Interpolation for Polynomial Calculus and Sums-Of-Squares

Authors: Tuomas Hakoniemi

Published in: LIPIcs, Volume 168, 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)

Abstract

We prove that both Polynomial Calculus and Sums-of-Squares proof systems admit a strong form of feasible interpolation property for sets of polynomial equality constraints. Precisely, given two sets P(x,z) and Q(y,z) of equality constraints, a refutation Π of P(x,z) ∪ Q(y,z), and any assignment a to the variables z, one can find a refutation of P(x,a) or a refutation of Q(y,a) in time polynomial in the length of the bit-string encoding the refutation Π. For Sums-of-Squares we rely on the use of Boolean axioms, but for Polynomial Calculus we do not assume their presence.

Cite as

Tuomas Hakoniemi. Feasible Interpolation for Polynomial Calculus and Sums-Of-Squares. In 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 168, pp. 63:1-63:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{hakoniemi:LIPIcs.ICALP.2020.63,
  author =	{Hakoniemi, Tuomas},
  title =	{{Feasible Interpolation for Polynomial Calculus and Sums-Of-Squares}},
  booktitle =	{47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)},
  pages =	{63:1--63:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-138-2},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{168},
  editor =	{Czumaj, Artur and Dawar, Anuj and Merelli, Emanuela},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2020.63},
  URN =		{urn:nbn:de:0030-drops-124707},
  doi =		{10.4230/LIPIcs.ICALP.2020.63},
  annote =	{Keywords: Proof Complexity, Feasible Interpolation, Sums-of-Squares, Polynomial Calculus}
}

Document

DOI: 10.4230/LIPIcs.CCC.2019.24

Size-Degree Trade-Offs for Sums-of-Squares and Positivstellensatz Proofs

Authors: Albert Atserias and Tuomas Hakoniemi

Published in: LIPIcs, Volume 137, 34th Computational Complexity Conference (CCC 2019)

Abstract

We show that if a system of degree-k polynomial constraints on n Boolean variables has a Sums-of-Squares (SOS) proof of unsatisfiability with at most s many monomials, then it also has one whose degree is of the order of the square root of n log s plus k. A similar statement holds for the more general Positivstellensatz (PS) proofs. This establishes size-degree trade-offs for SOS and PS that match their analogues for weaker proof systems such as Resolution, Polynomial Calculus, and the proof systems for the LP and SDP hierarchies of Lovász and Schrijver. As a corollary to this, and to the known degree lower bounds, we get optimal integrality gaps for exponential size SOS proofs for sparse random instances of the standard NP-hard constraint optimization problems. We also get exponential size SOS lower bounds for Tseitin and Knapsack formulas. The proof of our main result relies on a zero-gap duality theorem for pre-ordered vector spaces that admit an order unit, whose specialization to PS and SOS may be of independent interest.

Cite as

Albert Atserias and Tuomas Hakoniemi. Size-Degree Trade-Offs for Sums-of-Squares and Positivstellensatz Proofs. In 34th Computational Complexity Conference (CCC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 137, pp. 24:1-24:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{atserias_et_al:LIPIcs.CCC.2019.24,
  author =	{Atserias, Albert and Hakoniemi, Tuomas},
  title =	{{Size-Degree Trade-Offs for Sums-of-Squares and Positivstellensatz Proofs}},
  booktitle =	{34th Computational Complexity Conference (CCC 2019)},
  pages =	{24:1--24:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-116-0},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{137},
  editor =	{Shpilka, Amir},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2019.24},
  URN =		{urn:nbn:de:0030-drops-108464},
  doi =		{10.4230/LIPIcs.CCC.2019.24},
  annote =	{Keywords: Proof complexity, semialgebraic proof systems, Sums-of-Squares, Positivstellensatz, trade-offs, lower bounds, monomial size, degree}
}

Search Results

Documents authored by Hakoniemi, Tuomas

Feasible Interpolation for Polynomial Calculus and Sums-Of-Squares

Abstract

Cite as

Size-Degree Trade-Offs for Sums-of-Squares and Positivstellensatz Proofs

Abstract

Cite as

Thanks for your feedback!

Could not send message